package leetcode_201_300;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LeeCode_239 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1}, 1)));
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
    }
    private static int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0])
                return o1[1] - o2[1];
            return o2[0] - o1[0];
        });
        int n = nums.length;
        int l = 0, r = k - 1;
        for (int i = 0; i <= r; i++) {
            queue.add(new int[]{nums[i], i});
        }
        int[] ans = new int[n - r];
        int i = 0;
        while (r < n){
            while (queue.peek()[1] < l)
                queue.poll();
            ans[i] = queue.peek()[0];
            i++;
            l++;
            r++;
            if (r < n)
                queue.add(new int[]{nums[r], r});
        }
        return ans;
    }
}